[Salesforce] Listのintersection（積集合）の高速化

#Apex

進地崇裕

2021.06.02

この記事は公開されてから1年以上経過しています。情報が古い可能性がありますので、ご注意ください。

小ネタです。

Listのintersection

Apexで二つのListのintersection（積集合、共通集合とも）はSetを使って次のように実装できます。

List<SomeObj> listA = getSomeObjListA(); // getSomeObjListA はN個のSomeObjを返すものとする
List<SomeObj> listB = getSomeObjListB(); // getSomeObjListB はN個のSomeObjを返すものとする

List<SomeObj> listAB = new List<SomeObj>(); // listA と listB のintersection を入れるリスト

Set<SomeObj> setOfListA = new Set<SomeObj>(listA); // Setを使うことでループの計算量をO(N)にする
for ( SomeObj obj : listB ) {
    if ( setOfListA.contains(obj) ) {
       listAB.add(obj);
    }
}

計算量がO(1)のSet.containsを使うことで、forループの計算量が全体で O(N x 1) = O(N) になっています。

これを、次のように計算量がO(N)のList.indexOfを使うと、forループの計算量が O(N x N) = O(N^2) になってしまいます。

List<SomeObj> listA = getSomeObjListA(); // getSomeObjListA はN個のSomeObjを返すものとする
List<SomeObj> listB = getSomeObjListB(); // getSomeObjListB はN個のSomeObjを返すものとする

List<SomeObj> listAB = new List<SomeObj>(); // listA と listB のintersection を入れるリスト

for ( SomeObj obj : listB ) {
    Integer index = listA.indexOf(obj); // List.indexOfは計算量がO(N)かかる
    if ( index != -1 ) {
       listAB.add(obj);
    }
}

こうなると、N = 数百ぐらいのオーダーでSalesforceのガバナ制限の一つである、「Salesforce サーバの最大 CPU 時間」の10,000msに抵触してしまい、実行時エラーになります。

indexOfが遅いのは常にListの先頭から順に一致するかを見ていくからで、ペンキ屋のシュレミールがいるからです¹。

ちなみに、Javaでは HashSet.IntersectWith を使うという手もあります。
同様のことはApexでは Set.retainAll で表現できますが、ここにも実装のどこかにペンキ屋のシュレミールがいるようで、まともに動きませんでした。